﻿#define _CRT_SECURE_NO_WARNINGS 1
//矩阵区域和（medium）:https://leetcode.cn/problems/matrix-block-sum/description/

class Solution {
public:
	vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
		int m = mat.size(), n = mat[0].size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1));
		// 1. 预处理前缀和矩阵
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] +
				mat[i - 1][j - 1];

		// 2. 使⽤
		vector<vector<int>> ret(m, vector<int>(n));
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
			{
				int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
				int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
				ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +
					dp[x1 - 1][y1 - 1];
			}

		return ret;
	}
};